﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Reflection;

namespace TwinHead.Frameworks.Collections
{
    /// <summary>
    /// IList T를 구현한 컬렉션의 정렬을 SQL의 Order By와 같은 방식으로 처리해주는 클래스
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public sealed class CollectionSort<T>
    {
        private CollectionSort() { }

        /// <summary>
        /// T유형의 프로퍼티를 필드로 하여 정렬을 처리합니다.
        /// <para>필드명 [ASC|DESC] (ex: "Author Asc, Title Desc")</para>
        /// </summary>
        /// <param name="list">IList</param>
        /// <param name="sortExpression">필드명 [ASC|DESC] (ex: "Author Asc, Title Desc")</param>
        /// <param name="valueComparer">지정한 필드의 값을 비교할때 사용하는 비교자입니다.</param>
        public static void Sort( IList<T> list, string sortExpression, IComparer valueComparer )
        {
            SortInfo[] sorts = BuildSorts( sortExpression, valueComparer );

            for (int i = sorts.Length - 1; i >= 0; i--)
            {
                SortInfo si = sorts[i];
                MergeSort<T>.Sort( list, si.Comparer, si.Direction );
            }
        }
        /// <summary>
        /// T유형의 프로퍼티를 필드로 하여 정렬을 처리합니다.
        /// <para>필드명 [ASC|DESC] (ex: "Author Asc, Title Desc")</para>
        /// </summary>
        /// <param name="list">IList</param>
        /// <param name="sortExpression">필드명 [ASC|DESC] (ex: "Author Asc, Title Desc")</param>
        public static void Sort( IList<T> list, string sortExpression )
        {
            Sort( list, sortExpression, null );
        }

        private static SortInfo[] BuildSorts( string sortExpression, IComparer valueComparer )
        {
            Type itemType = typeof( T );
            string[] sortArray = sortExpression.Split( ',' );
            int arrayLength = sortArray.Length;
            List<SortInfo> comparers = new List<SortInfo>( arrayLength );

            string sortExp;
            string propertyName;

            for (int i = 0; i < arrayLength; i++)
            {
                sortExp = sortArray[i].Trim();

                ListSortDirection direction;

                int spacePos = sortExp.IndexOf( ' ' );

                if (spacePos >= 0)
                {
                    propertyName = sortExp.Substring( 0, spacePos );
                    string sortOrder = sortExp.Substring( spacePos + 1 );

                    if (String.Compare( sortOrder, "asc", StringComparison.OrdinalIgnoreCase ) == 0)
                        direction = ListSortDirection.Ascending;
                    else if (String.Compare( sortOrder, "desc", StringComparison.OrdinalIgnoreCase ) == 0)
                        direction = ListSortDirection.Descending;
                    else
                        throw new ArgumentException( "Sort order '" + sortOrder + "' is invalid. Must be ASC or DESC." );
                }
                else
                {
                    propertyName = sortExp;
                    direction = ListSortDirection.Ascending;
                }

                PropertyComparer<T> comparer = null;
                if (valueComparer != null)
                {
                    comparer = new PropertyComparer<T>( propertyName, valueComparer );
                }
                else
                {
                    comparer = new PropertyComparer<T>( propertyName );
                }
                comparers.Add( new SortInfo( comparer, direction ) );
            }

            return comparers.ToArray();
        }
        private class SortInfo
        {
            public SortInfo( PropertyComparer<T> comparer, ListSortDirection direction )
            {
                this.Comparer = comparer;
                this.Direction = direction;
            }

            public PropertyComparer<T> Comparer;
            public ListSortDirection Direction;
        }
    }

    /// <summary>
    /// merge sort algorithm을 구현한 클래스
    /// </summary>
    internal sealed class MergeSort<T>
    {
        private IComparer<T> _comparer;
        private bool _isAscending;
        private IList<T> _list;
        private T[] _buffer;
        /// <summary>
        /// 생성자.
        /// </summary>
        /// <param name="list"></param>
        /// <param name="comparer"></param>
        /// <param name="direction"></param>
        private MergeSort( IList<T> list, IComparer<T> comparer, ListSortDirection direction )
        {
            _list = list;
            _buffer = new T[list.Count];
            _comparer = comparer;
            _isAscending = (direction == ListSortDirection.Ascending);
        }
        public static void Sort( IList<T> list, IComparer<T> comparer, ListSortDirection direction )
        {
            MergeSort<T> sort = new MergeSort<T>( list, comparer, direction );
            sort._MergeSort( 0, list.Count - 1 );
        }
        private int Compare( T x, T y )
        {
            if (_isAscending)
                return _comparer.Compare( x, y );
            else
                return _comparer.Compare( y, x );
        }

        #region 성능이 좀 고민되는 부분...(merge sort 알고리즘을 구현한 부분이다 ㅡ.ㅡ)
        private void _MergeSort( int firstIndex, int lastIndex )
        {
            int lastRelativeIndex = lastIndex - firstIndex;

            if (lastRelativeIndex < 1)
                return;

            int middle = (lastRelativeIndex / 2) + firstIndex;
            int postMiddle = middle + 1;

            _MergeSort( firstIndex, middle );
            _MergeSort( postMiddle, lastIndex );

            Merge( firstIndex, middle, postMiddle, lastIndex );
        }

        private void Merge( int leftStart, int leftEnd, int rightStart, int rightEnd )
        {
            int bufferIndex = leftStart;
            int leftIndex = leftStart;
            int rightIndex = rightStart;

            while (leftIndex <= leftEnd && rightIndex <= rightEnd)
            {
                if (Compare( _list[leftIndex], _list[rightIndex] ) > 0)
                    _buffer[bufferIndex++] = _list[rightIndex++];
                else
                    _buffer[bufferIndex++] = _list[leftIndex++];
            }

            for (int i = leftIndex; i <= leftEnd; i++)
                _buffer[bufferIndex++] = _list[i];

            for (int i = rightIndex; i <= rightEnd; i++)
                _buffer[bufferIndex++] = _list[i];

            for (int i = leftStart; i <= rightEnd; i++)
                _list[i] = _buffer[i];
        }
        #endregion
    }

    /// <summary>
    /// 객체의 프로퍼티값으로 비교해주는 비교자 처리 클래스.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    [DebuggerDisplay( "{GetDebuggerText()}" )]
    internal class PropertyComparer<T> : IComparer<T>
    {
        private string _propertyName;
        private MethodInfo _getMethod;
        private IComparer _comparer;

        public PropertyComparer( string propertyName )
            : this( propertyName, null )
        { }

        public PropertyComparer( string propertyName, IComparer valueComparer )
        {
            ExtractMethod( typeof( T ), propertyName );

            if (valueComparer != null)
                _comparer = valueComparer;
            else
                _comparer = Comparer.Default;
        }

        private void ExtractMethod( Type t, string propertyName )
        {
            PropertyInfo pi = t.GetProperty( propertyName, BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance | BindingFlags.IgnoreCase );

            if (pi == null)
                throw new InvalidOperationException( "Cannot find a instance property named '" + _propertyName + "'." );

            _propertyName = pi.Name;

            MethodInfo mi = pi.GetGetMethod();
            if (mi == null)
                throw new InvalidOperationException( "The property '" + _propertyName + "' does not have a get accessor." );

            _getMethod = mi;
        }

        public int Compare( T x, T y )
        {
            object xValue = _getMethod.Invoke( x, null );
            object yValue = _getMethod.Invoke( y, null );

            return _comparer.Compare( xValue, yValue );
        }
        private string GetDebuggerText()
        {
            return String.Format( "{0}.{1}", _getMethod.DeclaringType.Name, _propertyName );
        }
    }
}